#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

int* Next(char* p)
{
    int m=strlen(p),j=0;
    int* N=new int[m];
    int t=N[0]=-1;
    while(j<m-1)
    {
        if(0>t||p[j]==p[t])
        {
            N[++j]=++t;
        }
        else
        {
            t=N[t];
            }
    }
    return N;
}

int KMP(char t[],char p[])
{
    int* next=Next(p);
    int n=strlen(t),i=0;
    int m=strlen(p),j=0;
    while(j<m&&i<n)
    {
        if(j<0||t[i]==p[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
    }
    delete []next;
    return i-j;
}

int main()

{
    char org[]="AABBCCDDEE";
    char str[]="CDDE";
    int ans=KMP(org,str);
    cout<<ans<<endl;

    system("pause");
    return 0;
}
